/*
 * 给你一个整数数组 nums，有一个大小为 k
 * 的滑动窗口从数组的最左侧移动到数组的最右侧。 你只可以看到在滑动窗口内的 k
 * 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
 *
 * 示例 1：
 *   输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
 *   输出：[3,3,5,5,6,7]
 *   解释：
 *     滑动窗口的位置                最大值
 *     ---------------               -----
 *     [1  3  -1] -3  5  3  6  7       3
 *      1 [3  -1  -3] 5  3  6  7       3
 *      1  3 [-1  -3  5] 3  6  7       5
 *      1  3  -1 [-3  5  3] 6  7       5
 *      1  3  -1  -3 [5  3  6] 7       6
 *      1  3  -1  -3  5 [3  6  7]      7
 *
 * 示例 2：
 *
 *   输入：nums = [1], k = 1
 *   输出：[1]
 *
 * 提示：
 *
 *   1 <= nums.length <= 105
 *   -104 <= nums[i] <= 104
 *   1 <= k <= nums.length
 */

#include <stdio.h>
#include <stdlib.h>

#pragma pack(1)
typedef struct {
  int value;  // 值
  int index;  // 数组下标，用于判断是否在滑动窗口内
} Pair;

typedef struct {
  Pair* pairs;
  int size;
  int capacity;
} PriorityQueue;
#pragma pack()

PriorityQueue* CreatePriorityQueue(int capacity) {
  PriorityQueue* q = (PriorityQueue*)malloc(sizeof(PriorityQueue));
  q->pairs = (Pair*)malloc((capacity) * sizeof(Pair));
  q->size = 0;
  q->capacity = capacity;
  return q;
}

void DestroyPriorityQueue(PriorityQueue* q) {
  if (q != NULL) {
    if (q->pairs != NULL) {
      free(q->pairs);
    }
    free(q);
  }
}

void SiftUp(PriorityQueue* q, int index) {
  if (index == 0) return;
  int parentIndex = (index - 1) / 2;
  Pair _pair;
  // 当前index位置的元素的值如果小于父节点的值，则返回。
  if (q->pairs[index].value <= q->pairs[parentIndex].value) {
    return;
  }

  // 否则，与父节点互换位置。以新的index位置再进行SiftUp操作。
  _pair = q->pairs[index];
  q->pairs[index] = q->pairs[parentIndex];
  q->pairs[parentIndex] = _pair;
  SiftUp(q, parentIndex);
}

void SiftDown(PriorityQueue* q, int index) {
  int leftChildIndex = index * 2 + 1, rightChildIndex = index * 2 + 2;
  Pair _pair;
  int _index = 0;
  // 当前index不存在子节点了，则返回。
  // 当前index存在左子节点，不存在右子节点，则比较当前index与左子节点的的值，若大于则返回，若小于则互换，并返回。
  if (rightChildIndex > q->size - 1) {
    if (leftChildIndex <= q->size - 1 &&
        q->pairs[index].value < q->pairs[leftChildIndex].value) {
      _pair = q->pairs[index];
      q->pairs[index] = q->pairs[leftChildIndex];
      q->pairs[leftChildIndex] = _pair;
    }
    return;
  }

  // 当前index左右子节点都存在，则选取左右子节点中较大的那个进行互换，然后以新的位置继续进行SiftDown
  if (q->pairs[leftChildIndex].value < q->pairs[rightChildIndex].value) {
    _index = rightChildIndex;
  } else {
    _index = leftChildIndex;
  }
  if(q->pairs[index].value < q->pairs[_index].value)
  {
    _pair = q->pairs[index];
    q->pairs[index] = q->pairs[_index];
    q->pairs[_index] = _pair;
    SiftDown(q, _index);
  } 
}

void Pop(PriorityQueue* q, int windowStartIndex) {
  // 将堆底的最后一个元素放在堆顶，然后开始进行siftDown操作。
  q->pairs[0] = q->pairs[--q->size];
  SiftDown(q, 0);

  // 检查堆顶元素，如果堆顶元素的index不在滑动窗口范围内，则继续进行Pop操作。
  if (q->pairs[0].index < windowStartIndex) {
    Pop(q, windowStartIndex);
  }
}

void Push(PriorityQueue* q, int value, int index, int windowStartIndex) {
  Pair _pair = {value, index};

  // 如果一进来就比堆顶元素大，则直接替换堆顶元素即可。
  if (_pair.value > q->pairs[0].value) {
    q->pairs[0] = _pair;
    if (index == 0) q->size++;
    return;
  }

  // 将当前元素放在堆底，然后开始进行siftUp操作。
  q->pairs[q->size++] = _pair;
  SiftUp(q, q->size - 1);

  // 最后检查堆顶元素，如果堆顶元素的index不在滑动窗口范围内，则进行Pop操作。
  if (q->pairs[0].index < windowStartIndex) {
    Pop(q, windowStartIndex);
  }
}

int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
  *returnSize = numsSize - k + 1;
  int* ret = (int*)malloc(sizeof(int) * (*returnSize));
  PriorityQueue* q = CreatePriorityQueue(numsSize);
  int windowStartIndex = 0;
  for (int i = 0; i < numsSize; i++) {
    windowStartIndex = (i - k + 1) >= 0 ? (i - k + 1) : 0;
    Push(q, nums[i], i, windowStartIndex);

    if (i >= k - 1) {
      ret[i - k + 1] = q->pairs[0].value;
    }
  }
  return ret;
}

int main() {
  int nums[] = {9999, 9998, 9997, 9996, 9995, 9994,
                9993, 9992, 9991, 9990, 9989};
  int k = 6;
  int n = sizeof(nums) / sizeof(nums[0]);
  int returnSize;
  int* result = maxSlidingWindow(nums, n, k, &returnSize);

  printf("Max sliding window: ");
  int i;
  for (i = 0; i < returnSize; ++i) {
    printf("%d ", result[i]);
  }
  printf("\n");

  free(result);
  return 0;
}
